package com.jxb.test20241216;

import java.util.Arrays;

public class Sort8 {

    public static void main(String[] args) {

    }

    public static int[] sortArray(int[] nums) {
        if (nums == null) {
            return null;
        }
        return partSort(nums);
    }

    private static Integer threshold = 3;


    private static int[] partSort(int[] nums) {
        if (nums.length <= threshold) {
            return nums;
        }
        //进行分治
        int length = nums.length / 2;
        int[] left = Arrays.copyOfRange(nums, 0, length);
        int[] right = Arrays.copyOfRange(nums,length,nums.length);

        //合并排序
        return sortP(partSort(left),partSort(right));
    }

    private static int[] sortP(int[] left, int[] right) {
        int[] res = new int[left.length + right.length];
        if (threshold > 1) {
            sortSubArray(left);
            sortSubArray(right);
        }
        for (int index = 0, i = 0,j = 0; index < res.length; index ++) {
            if (i >= left.length) {
                res[index] = right[j++];
            }else if (j >= right.length) {
                res[index] = left[i++];
            }else if (left[i] > right[j]) {
                res[index] = right[j++];
            }else {
                res[index] = left[i++];
            }
        }
        return res;
    }

    private static void sortSubArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0;i<arr.length;i++) {
            int preIndex = i;
            int currentValue = arr[i+1];
            while (preIndex > 0 && currentValue < arr[preIndex]) {
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1] = currentValue;
        }
    }

}
